package com.computer.fundamentals.algorithm;

/**
 * 圆环回原点问题：
 *     0 ~ N的数构成一个环，从0出发，每次走1步，走s步后走回0的可能方案数
 */
public class CircleBackToTheOriginalPoint {

    /**
     * 解决方案
     */
    public static int solution(int n, int s) {
        int[][] dp = new int[s+1][n+1];
        dp[0][0] = 1;
        for (int i = 1;i < dp.length;i++) {
            for (int j = 0;j < dp.length;j++) {
                dp[i][j] = dp[i-1][(j+n) % (n+1)] + dp[i-1][(j+1) % (n+1)];
            }
        }
        return dp[s][0];
    }

    /**
     * 测试
     */
    public static void main(String[] args) {

        System.out.println("------------测试------------");
        System.out.println(solution(9, 5));
    }
}